題目

https://leetcode.com/problems/symmetric-tree/

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

解答

C#

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsSymmetric(TreeNode root)
    {
        if (root == null)
            return true;

        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.Push(root.left);
        stack.Push(root.right);

        while (stack.Count > 0)
        {
            TreeNode right = stack.Pop();
            TreeNode left = stack.Pop();

            if (left == null && right == null)
                continue;
            if ((right == null && left != null)
                ||(right != null && left == null))
                return false;
            if (right.val != left.val)
                return false;

            stack.Push(left.left);
            stack.Push(right.right);
            stack.Push(left.right);
            stack.Push(right.left);
        }
        return true;
    }
}

結果

Runtime: 92 ms, faster than 95.15% of C# online submissions.

Memory Usage: 24.1 MB, less than 27.27% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(n)

為什麼我要這樣做？

在講解之前，大家可以先複習一下

使用 Stack 的另一篇相似文章 ↓
[Day 4] 演算法刷題 LeetCode 20. Valid Parentheses (Easy)
什麼是 Tree？這題的遞迴解法 ↓
[Day 22] 演算法刷題 LeetCode 101. Symmetric Tree (Easy) Part 1 - Recursion

不知道有沒有人對遞迴理解有障礙及困難？今天是用 疊代法 Iteration 去解這題演算法。

1. 只要 root 為 null ，回傳 true
2. 宣告一個 stack，因為這題主要是判斷 tree 是不是為對稱，也就換句話說，兩邊相對位置的節點的值一樣就是對稱，所以我這邊用 stack 去做輔助與判斷。
3. Push 左節點 到 stack
4. Push 右節點 到 stack
5. 宣告 while 迴圈，只要 stack 裡還有值則繼續 loop
   • pop 右節點為 right
   • pop 左節點為 left
     • 因為一開始先 push 左節點，根據 stack 後進先出 的概念，所以 pop 時就要 相反
   • 如果 left 與 right 為 null 時，繼續 下一輪迴圈 做判斷
     • 因為此時雖然成對，但是 stack 裡可能還有其他 node 等待做判斷
   • 如果 left 與 right 不成對，則回傳 false
     • 其中一個為 null 一個不為 null → 不成對
     • right.val != left.val 兩個值不一樣 → 不成對
   • Push left 的左右節點，等待下一輪判斷
   • Push right 的左右節點，等待下一輪判斷
6. 迴圈跑完都沒有不成對的節點且 stack 為空時，回傳 true

示意圖

如果看文字敘述不是很明確的話，可以看下面的示意圖。

以 [1, 2, 2, 3, 4, 4, 3] 為例，程式就會照下列的順序去巡覽。

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Step 7

Step 8

Step 9

Step 10

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉